1. Field of the Invention
This invention relates to a method and apparatus for providing interoperability between key recovery and non-key recovery systems. More particularly, the invention relates to a method and apparatus for ensuring, in a cryptographic communication system in which a sender transmits data encrypted under an encryption key to a receiver, the concomitant transmission of data sufficient to permit recovery of the encryption key by a key recovery entity.
2. Description of the Related Art
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private-key) encryption systems use the same secret key for both encrypting and decrypting messages. Perhaps the best-known symmetric encryption system is the Data Encryption Algorithm (DEA), implementing the Data Encryption Standard (DES) as described in the National Institute of Standards and Technology (NIST) publications xe2x80x9cData Encryption Standard (DES)xe2x80x9d, FIPS PUB 46-2 (1980), and xe2x80x9cDES Modes of Operationxe2x80x9d, FIPS PUB 81 (1988). In the DES system, a 64-bit key is used to transform a plaintext message comprising one or more 64-bit plaintext blocks into a ciphertext message comprising a like number of 64-bit ciphertext blocks, or vice versa. Of the 64 key bits, 56 bits are independently specifiable, while the remaining 8 bits provide a parity check.
Asymmetric (or public-key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver""s public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman and described in B. Schneier, Applied Cryptography (1996), pages 466-474, incorporated herein by reference.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies, since the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (i.e., systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving key-related recovery information to the key recovery agents ahead of time (in which case the recovery information is said to be xe2x80x9cescrowedxe2x80x9d) or by providing sufficient information in the communication itself (as by encrypting the key portions) which the key recovery agents could obtain after the communication occurred. Key recovery agents would reveal the escrowed or regenerated key information to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception. The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent or that a compromise in the physical security of a single key recovery agent will expose the key.
Key recovery systems serve the communicants"" interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial files where keys are not recoverable. Loss of keys may result in loss of important stored data.
Key recovery systems of various types are described in U.S. Pat. Nos. 5,557,346 (Lipner et al.); 5,815,573 (Johnson et al.); and 5,796,830 (Johnson et al.), as well as in copending U.S. patent applications Ser. Nos. 08/725,102, filed Oct. 2, 1996 (Gennaro et al.); 08/775,348, filed Jan. 3, 1997 (Gennaro et al.); and 08/899,855, filed Jul. 24, 1997 (Chandersekaran et al.), all of which are incorporated herein by reference.
An important aspect of key recovery systems is the method used to ensure that correct recovery information is provided. If the recovery information provided is not correct, either through unintentional error, or deliberate attempt to corrupt, the functionality of the key recovery system can be thwarted. Ordinarily, in the absence of some earlier validation check, any deficiency in the key recovery information is only detected when key recovery is attempted by a key recovery entity, which is generally too late to cure the deficiency.
Validation can be provided in several ways, including direct checking by the participants, checking by the recovery agents, and checking by the recovery entity. Access to accurate key recovery information can also be ensured by redundant calculation and disclosure of the recovery information by more than one of the communicating parties.
In a network of interconnected computer systems, where some computer systems are key recovery enabled (KR-enabled)xe2x80x94i.e., are capable of generating key recovery information xe2x80x94and some are non-KR-enabled, it would be desirable to permit a KR-enabled computer to interoperate with both KR-enabled and non-KR-enabled computers only if key recovery is enforced.
FIG. 1 shows a cryptographic system 100 comprising a KR-enabled computer system 102 coupled to a non-KR-enabled computer system 104 via a communications channel 106. We assume the following model of trusted and untrusted components:
1. The KR-enabled system 102 has a key recovery subsystem 108 that provides key recovery and other cryptographic services to one or more application programs 110. KR subsystem 108 may be implemented as software, as hardware, or as some combination of the two.
2. The non-KR-enabled system 104 has a cryptographic subsystem 112 that provides cryptographic services to one or more application programs 114. Like KR subsystem 108, cryptographic subsystem 110 may be implemented as software, as hardware, or as some combination of the two.
3. The KR-enabled key recovery subsystem 108 and its supporting cryptographic subsystem (not separately shown, but included within the KR subsystem) will enforce the use of the key recovery protocol, regardless of whether it is communicating with a KR-enabled or a non-KR-enabled system.
4. The key recovery subsystem 108 of the KR-enabled system 102 is a trusted component. It can be trusted to enforce the key recovery protocol.
5. The application programs 110 running on the KR-enabled system 102, the cryptographic subsystem 112 of the non-KR-enabled system 104, and the application programs 114 running on the non-KR-enabled system 104 are not trusted components. These components cannot be trusted to enforce the key recovery protocol. In fact, it is assumed that the applications 110 and 114 running on the KR-enabled and non-KR-enabled systems 102 and 104, respectively, might attempt to circumvent the key recovery protocol, if such a circumvention were possible.
Consider an ideal situation in which a KR-enabled system 102 (Alice) communicates with a non-KR-enabled system 104 (Bob), where Alice""s application program 110 is assumed (for the sake of argument) to perform the key recovery protocol correctly.
Alice""s system 102 performs the following steps:
1. Alice generates a key K, which is to be used for strong encryption.
2. Alice generates a key exchange block (KEB), containing K, which is used to transport K in encrypted form to Bob.
3. Alice generates a key recovery block (KRB), which contains all the information needed to enable key recovery.
4. Alice encrypts data with K to produce ciphertext e(K, data).
5. Alice sends KEB, KRB, and e(K, data) to Bob.
Upon receipt of KEB, KRB, and e(K, data), Bob""s system 104 performs the following steps:
1. Since Bob is non-KR-enabled, Bob ignores KRB.
2. Bob recovers K from KEB.
3. Bob decrypts e(K, data) to recover the data.
Now consider the case where Alice""s application 110 does not behave properly. We observe that Alice""s application 110 can easily circumvent the key recovery protocol by simply not sending KRB to Bob. Without KRB, there is no effective means for law enforcement to recover the key, even with a lawful warrant or court order. Bob, on the other hand, did not need KRB for anything, so its absence creates no problem.
If Bob is KR-enabled, and honest, then Bob could be designed to operate with Alice only if Alice sends Bob a correct KRB. One approach is for Bob recreate the KRB and compare it for equality with the KRB received from Alice. Bob""s version of the key K is enabled for use only if the KRBs compare equal. However, the procedure for recreating the KRB typically involves a computationally expensive public-key encryption operation. Also, the procedure requires that Bob""s system be trusted to perform the verification operation.
One possible alternative method of solution is for Alice""s key recovery system to alter the plaintext prior to encryption, in such a way that Bob can recover the plaintext only if he also receives a correct copy of KRB. However, if Alice and Bob conspire to defeat the KR solution method, then the possible methods that we describe here can be attacked. Hence, it does not appear that a workable solution can be obtained by altering the plaintext. For example, the data could be combined with KRB using an invertible function F to produce F(data, KRB), where the quantity F(data, KRB) is then encrypted with the key K. In this case, Alice sends e(F(data, KRB)) to Bob instead of e(K, data). To illustrate this method still further, suppose that the data, X, is divided into blocks X1, X2, . . . , Xn, where the length of each Xi (except for the last block Xn) is equal to the length of KRB. Then KRB, or some appropriate sub-portion, is Exclusive-ORed (XORed) with each Xi to produce (X1 ⊕KRB), (X2 ⊕KRB), etc., and the masked plaintext is then encrypted with the key K. (The symbol xe2x80x9c⊕xe2x80x9d denotes XOR addition.) The idea here is that Alice would be required to send KRB to Bob in order for Bob to invert the process and recover the clear data. However, a problem with this method is that Alice and Bob could agree to exchange an encrypted KRB instead of a clear KRB. In this case, Alice sends KEB, e(K, KRB), and e(K, F(data, KRB)) to Bob. Using KEB, Bob imports K into his system, and then decrypts e(K, KRB) and e(K, F(data, KRB)) using K. Bob then uses the clear value of KRB to recover the original data from F(data, KRB). In this case, as long as Alice is able to send an encrypted copy of KRB to Bob, Bob can invert the function performed by Alice""s system, regardless of what function is used.
Another problem with perturbing the plaintext with the KRB using an invertible function (e.g., an Exclusive-OR function) before encrypting it is that Alice is not prevented from modifying the plaintextxe2x80x94in the same wayxe2x80x94with the KRB before invoking the encryption operation. In that case, Alice would Exclusive-OR the KRB with the blocks of plaintext, X1, X2, etc. so that when the KR system performs the KRB-based perturbation again, the real plaintext is the text finally encrypted, thus effectively foiling the scheme.
Another possible alternative method of solution is for Alice""s key recovery system to alter the ciphertext after encryption, such that Bob could recover the plaintext only if he also receives a clear copy of KRB. However, there seems to be no way to accomplish this, since any alteration of the ciphertext that Bob could invert using KRB could also be inverted by Alice using KRB. And Alice, could merely send Bob the unaltered ciphertext without KRB instead of sending Bob the altered ciphertext with KRB.
The present invention describes a method in which Bob is able to decrypt the encrypted data, e(K, data), received from Alice only if a valid KRB is provided to Bob. The solution enables Alice (who obeys the rules for key recovery) to communicate with Bob, who may or may not be enabled for key recovery. The solution does not allow Bob, who is not KR-enabled, to communicate with Alice, who is KR-enabled. This latter case is not possible since Bob, who is not KR-enabled, has no way to generate a KRB to send to Alice, and Alice""s decryption service is enabled only after receiving a valid KRB from Bob.
In accordance with the invention, the establishment of K in Bob""s system is made dependent on Bob having a clear copy of KRB. In this case, Alice cannot subvert the protocol by encrypting KRB with K, since then (without KRB) Bob has no way to recover K in his systemxe2x80x94i.e., Bob is confronted with a xe2x80x9cchicken and eggxe2x80x9d problem. Different methods can be used to tie the recovery of K to KRB, as described below.
The method of the present invention would replace the method described in the background section above, in which Bob recreates the KRB and compares it for equality with the KRB received from Alice. And because the method of the invention is an integral part of the decryption operation, it can provide a stronger form of checking. Also, Bob can avoid the costly public-key encryption steps that are required to recreate the KRB.